package Sort;

import java.util.Arrays;

public class leet_215 {
    public static void main(String[] args) {
        Solution_215 p = new Solution_215();
        int[] nums = new int[]{3,2,3,1,2,4,5,5,6};
//        int value = p.findKthLargest(nums, 4);
//        System.out.println(value);
        int[] values = p.heapSort(nums);
        System.out.println(Arrays.toString(values));

        int[] values_s = p.cutHeap(values, 4);
        System.out.println(Arrays.toString(values));

    }

}



class Solution_215 {
    public int findKthLargest(int[] nums, int k) {
        quickSort(nums, 0, nums.length-1);
        return nums[nums.length-k];
    }

    /**
     * 快速排序
     * @param nums  数组列表
     * @param left  左指针位置
     * @param right 右指针位置
     * @return  排好序的数组
     */
    public void quickSort(int[] nums, int left, int right){
        // 当左指针超过右指针时代表2边已经排好序了
        if(left>right){
            return;
        }
        // 记录基准数
        int medium = nums[left];
        // 方便下面进行数据位置的替换
        int i=left;
        int j=right;


        while(i!=j){
            while(nums[j]>=medium && i<j){
                // 看看那些数是比medium大的，大的话右指针向左移动代表不需要进行改变
                j--;
            }

            while(nums[i]<=medium && i<j){
                // 看看那些数是比medium小的，小的话左指针向右移动代表不需要进行改变
                i++;
            }

            if(i<j){
                // 将找到的2个位置的数据进行交换
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }

        // 将medium值赋给i指针的位置这个位置是分割数据的位置
        // 这里我理解是要和基准位的数据进行交换
        nums[left] = nums[i];
        nums[i] = medium;
        // 递归排序 （左指针不改变, 右指针代表没有排好序的其中i这个位置是已经排好顺序了）
        quickSort(nums, left, i-1);
        // 递归排序 （右指针不改变, 左指针代表没有排好序的其中i这个位置是已经排好顺序了）
        quickSort(nums, i+1, right);
    }


    // 使用大根堆的方式实现逻辑
    public int findKthLargestHeap(int[] nums, int k){
        int[] value = heapSort(nums);
        int[] cutHeap = cutHeap(value, k);
        return cutHeap[0];
    }

    /**
     * 剪枝大根堆
     * nums: 排好序的大根堆
     * k ： 需要剪枝的次数
     */
    public int[] cutHeap(int[] nums, int k){
        // 剪枝次数
        int times = 1;
        // 根堆的大小
        int maxSize = nums.length;
        while(times!=k){
            //首先将第一个元素与尾巴元素交换位置
            int tmp = nums[0];
            nums[0] = nums[maxSize-1];
            nums[maxSize-1] = tmp;
            // 缩减堆的大小
            maxSize--;
            // 调整堆
            adjustMaxHeap(nums, 0, maxSize);
            // 剪枝了需要计数
            times++;

        }
        return nums;
    }



    // 大根堆排序
    public int[] heapSort(int[] nums){
        // 非叶子节点开始调整  ((nums.length-1)-1)/2  计算公式
        int i = nums.length/2 -1;
        for(;i>=0; i--){
            adjustMaxHeap(nums, i, nums.length);
        }
        return nums;
    }


    /**
     * 比较元素(包括元素的调整后的比较)
     * @param nums 待排序数组
     * @param i    带排序的位置
     * @param size 数组大小用来判断是否存在右子树
     */
    public void adjustMaxHeap(int[] nums, int i, int size){
        // 左孩子
        int left = 2*i+1;
        // 右孩子
        int right = 2*i+2;
        int max = i;

        // 大根堆的逻辑，父节点要比2个子节点的数据大
        if(left<size && nums[left]>nums[max]){
            max = left;
        }
        if(right<size && nums[right]>nums[max]){
            max = right;
        }

        // 说明需要进行结点的调整
        if(max!=i){
            sift(nums, i, max);
            // 交换位置后需要判断交换完位置的结点是不是符合大根堆的逻辑
            adjustMaxHeap(nums, max, size);
        }

    }

    // 下沉元素
    public void sift(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }


}